/**
 * Created by L.jp
 * Description:输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重
 * 复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回
 * User: 86189
 * Date: 2021-12-16
 * Time: 19:49
 */
class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
        if(pre==null || vin==null){
            return null;
        }
        return recursion(pre,0,pre.length-1,vin,0,vin.length-1);
    }
    //递归
    public TreeNode recursion(int[] pre,int pre_start,int pre_end,int[] vin,int vin_start,int vin_end){
        if(pre_start>pre_end || vin_start>vin_end){
            return null;
        }
        TreeNode root=new TreeNode(pre[pre_start]);//构造好根节点
        //在中序数组中，根据先序数组先找到根节点，然后可以把数组分成两部分，一部分是中序左子树，一部分是中序右子树
        //同样在先序数组中也可以分成先序左子树和先序右子树，然后可以遍历中序数组递归构造左右子树了，每一次递归都是先找到子树的根节点然后遍历构造左右子树
        //在构造递归函数的参数时，尤其要注意的是构造左子树时先序数组的起始下标是根节点下标的下一个位置（pre_start+1)
        // 左子树先序数组终止下标是利用中序数组来求，也就是当前位置根节点下标减去中序数组起始下标，这是左子树节点的个数也是先序数组需要遍历的个数，让先序数组起始下标加上他再减一即是先序数组终止下标
        //左子树中序数组起始下标就是vin_start,终止下标就是i-1
        //构造右子树先序数组的起始下标就是左子树终止下标+1，终止下标就是pre_end,中序数组起始下标就是i+1,终止下标就是vin_end
        for(int i=vin_start;i<vin_end;i++){//每次遍历数组的起始和终止位置都是不一样的
            if(vin[i]==pre[pre_start]){//说明找到了每一个子树的根节点
                //递归构造左右子树
                //重点是参数的计算，下标的计算
                root.left=recursion(pre,pre_start+1,pre_start+i-vin_start,vin,vin_start,i-1);
                root.right=recursion(pre,pre_start+i-vin_start+1,pre_end,vin,i+1,vin_end);
                break;
            }
        }
        return root;
    }
}
